/*
 * @Author: szx
 * @Date: 2022-03-15 13:14:13
 * @LastEditTime: 2022-03-15 15:04:00
 * @Description:
 * @FilePath: \leetcode\1700-1799\1712\1712.js
 */
/**
 * @param {number[]} nums
 * @return {number}
 */
// var waysToSplit = function (nums) {
//     const n = nums.length;
//     let sum = 0;
//     const preSum = nums.map((value) => (sum += value));
//     let res = 0;
//     const mod = 1e9 + 7;
//     for (let i = 0; i < n - 2; i++) {
//         for (let j = i + 1; j < n; j++) {
//             const mid = preSum[j] - preSum[i];
//             if (preSum[i] <= mid && mid <= preSum[n - 1] - preSum[j]) {
//                 res++;
//                 res %= mod;
//             }
//         }
//     }
//     return res;
// };

var waysToSplit = function (nums) {
    const n = nums.length;
    let sum = 0;
    const preSum = nums.map((value) => (sum += value));
    let res = 0;
    const mod = 1e9 + 7;
    const t = Math.floor(preSum[n - 1] / 3);
    let m = 1;
    for (let l = 0; l < n - 2 && preSum[l] <= t; l++) {
        const leftSum = preSum[l];
        m = Math.max(m, l + 1);
        while (m < n && preSum[m] - leftSum < leftSum) m++;
        if (m == n) break;
        let low = m,
            high = n - 2;
        while (low <= high) {
            const mid = Math.floor((low + high) / 2);
            if (preSum[n - 1] - preSum[mid] < preSum[mid] - leftSum) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        res += high - m + 1;
    }
    return res % mod;
};

var waysToSplit = function (nums) {
    const n = nums.length;
    let sum = 0;
    const preSum = nums.map((value) => (sum += value));
    let res = 0;
    const mod = 1e9 + 7;
    const t = Math.floor(preSum[n - 1] / 3);
    let m = 1;
    for (let l = 0; l < n - 2 && preSum[l] <= t; l++) {
        const leftSum = preSum[l];
        m = Math.max(m, l + 1);
        while (m < n - 1 && preSum[m] - leftSum < leftSum) m++;
        let r = m;
        while (r < n - 1 && preSum[n - 1] - preSum[r] >= preSum[r] - leftSum) r++;
        res += r - m;
    }
    return res % mod;
};

console.log(waysToSplit([1, 1, 1]));
console.log(waysToSplit([0, 0, 0]));
console.log(waysToSplit([1, 2, 2, 2, 5, 0]));
console.log(waysToSplit([7, 2, 5, 5, 6, 2, 10, 9]));
console.log(waysToSplit([3, 2, 1]));
